package exclusiveor;

import org.junit.jupiter.api.Test;

import java.text.NumberFormat;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 题目：如果数组中只有一个数出现了奇数次，其他数都出现了偶数次，如何找到这个出现了奇数次的数？
 */
public class XORFindData01 {
    static NumberFormat instance = NumberFormat.getInstance();

    private static void geneterArrary(Random random, int anInt, int[] arr) {
        /**
         * 随机样本数据
         */
        arr[anInt] = random.nextInt(100);
        int i3 = random.nextInt(100);
        for (int i = 0; i < anInt; i++) {
            arr[i] = i3;
        }
        int i1 = random.nextInt(100);
        for (int i = anInt + 1; i < 2 * anInt + 1; i++) {
            arr[i] = i1;
        }
    }

    /**
     * 将这个数组整理成：{1,1,2,2,2,4,4,4,4,8,8,3,3,3,3}更加直观。
     * 因为异或的时候，与满足结合律和交换律，也就说，数组的顺序时候不会影响结果。
     * 那么：1^1=0,2^2^2=2,4^4^4^4=0,8^8=0,3^3^3^3=0那么可以发现，偶数个相同的数，
     * 异或结果为0，奇数个相同的数，结果为这个数本身。根据这个规律，将数组中所有的数据异或的到
     * 的结果便是要找的那个数。
     */
    public static int outOddNumber1(int[] arr) {
        int eor = 0;
        for (int j : arr) {
            // 利用异或的交换律和结合律，所有数据异或起来，那么个数为偶数的数据就会被消除，剩下个数为奇数的数据。
            eor = eor ^ j;
        }
        return eor;
    }

    /**
     * 对数器验证：思想，循环数组，找出那个出现了基奇数次的数据
     * 和算法找出来的比对。
     */
    private static int logarithmizer(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : arr) {
            // 循环数据，统计数据中每个数据出现的次数。
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }

        for (Map.Entry<Integer, Integer> entries : map.entrySet()) {
            // 找出出现了奇数次的那个数据返回。
            if ((entries.getValue() % 2) != 0) {
                return entries.getKey();
            }
        }
        return 0;
    }

    @Test
    public void client() {
        instance.setGroupingUsed(false);
        instance.setMaximumFractionDigits(0);
        Random random = new Random(1);
        for (int i = 0; i < 500; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(50);
            if (anInt % 2 != 0 || anInt < 2) {
                continue;
            }
            int[] arr = new int[2 * anInt + 1];
            geneterArrary(random, anInt, arr);
            System.out.println("=======================第" + (i + 1) + "次=======================");
            System.out.println("随机数组为==》" + Arrays.toString(arr));
            System.out.println("随机数组长度为==》" + 2 * anInt + 1);
            int eor = outOddNumber1(arr);
            System.out.println("算法查找数据为==》" + eor);
            int logarithmizer = logarithmizer(arr);
            if (logarithmizer == eor) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS");
            }
        }
    }
}
